package com.zjj.algorithm.learning.leetcode.sort;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer II 034. 外星语言是否排序 简单
 * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
 * <p>
 * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
 * <p>
 * 示例 1：
 * <p>
 * 输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
 * 输出：true
 * 解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
 * <p>
 * 示例 2：
 * <p>
 * 输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
 * 输出：false
 * 解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
 * 示例 3：
 * <p>
 * 输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
 * 输出：false
 * 解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小。
 *
 * @author zjj_admin
 * @date 2022/11/14 10:05
 */
public class AlienLanguageSort {

    public static void main(String[] args) {
        String[] words = new String[]{"apple", "app"};
        String order = "abcdefghijklmnopqrstuvwxyz";
        boolean res = isAlienSorted2(words, order);
        System.out.println("res = " + res);
    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 39.9 MB
     * 击败
     * 76.17%
     *
     * @param words
     * @param order
     * @return
     */
    public static boolean isAlienSorted2(String[] words, String order) {
        String word1 = "";
        String word2 = "";
        for (int i = 0; i < words.length - 1; i++) {
            //每次比较两个单词
            word1 = words[i];
            word2 = words[i + 1];
            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                int idx_s1 = j >= word1.length() ? -1 : order.indexOf(word1.charAt(j));
                int idx_s2 = j >= word2.length() ? -1 : order.indexOf(word2.charAt(j));

                //当相同位置第一个单词优先级小于第二个时，说明这两个单词手续没问题，直接比较下两个
                if (idx_s1 < idx_s2) {
                    break;
                    //若相等时，就比较下一个字母
                }
                if (idx_s1 > idx_s2) {
                    //当位置相同的字母，前者的优先级大于了后者，直接返回 false，说明是不正规的
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 时间
     * 1 ms
     * 击败
     * 35.40%
     * 内存
     * 41.6 MB
     * 击败
     * 5.7%
     *
     * @param words
     * @param order
     * @return
     */
    public static boolean isAlienSorted(String[] words, String order) {
        Map<String, Integer> map = new HashMap<>();
        //按照字符串的顺序为每一个字符设置优先级
        for (int i = 0; i < order.length(); i++) {
            map.put(order.substring(i, i + 1), i);
        }
        //给 0 设优先级为 -1，最低
        map.put("0", -1);
        String word1 = "";
        String word2 = "";
        for (int i = 0; i < words.length - 1; i++) {
            //每次比较两个单词
            word1 = words[i];
            word2 = words[i + 1];
            if (word1.length() > word2.length()) {
                //如果第二个单词个数小于第一个单词个数时，就在第二个单词末尾 加个 0
                word2 += "0";
            }
            for (int j = 0; j < word1.length(); j++) {
                if (word2.substring(j, j + 1).equals("0")) {
                    return false;
                }
                //当相同位置第一个单词优先级小于第二个时，说明这两个单词手续没问题，直接比较下两个
                if (map.get(word1.substring(j, j + 1)) < map.get(word2.substring(j, j + 1))) {
                    break;
                    //若相等时，就比较下一个字母
                } else if (map.get(word1.substring(j, j + 1)).equals(map.get(word2.substring(j, j + 1)))) {
                    continue;
                } else {
                    //当位置相同的字母，前者的优先级大于了后者，直接返回 false，说明是不正规的
                    return false;
                }
            }
        }
        return true;
    }
}
